抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

golang Map

技术Go

发布于：2025年3月3日

Map是有多个Key=>Value组成的一种数据结构，Key不可重复。

Go里面创建Map的方式

1
2
3
4
5
6
7
8
// 创建一个长度为1的Map
arr1 := make(map[int]string, 1)
// 创建一个不定长的Map
arr2 := make(map[int]string)
// 声明一个Map类型的变量，但不能直接使用，需要给他分配空间
var arr3 map[int]string
arr3 = make(map[int]string)
arr3[1] = "hello"

关于Map的结构

创建Map的是可以通过make，声明Map的容量。

通过源码得到结论：如果Map的容量小于8则不需要指定了，否则在创建Map是最好指定容量，这样可以提高性能。避免不停的扩容。

Golang的Map是通过Hash实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// A header for a Go map.
type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
    clearSeq   uint64

    extra *mapextra // optional fields
}

  • count：表示Map中Key=>Value数量

  • flags：表示Map是否处于写入/扩容状态

  • B：桶的数量为2^B

  • noverflow：溢出桶的数量

  • hash0：随机种子

  • buckets：bucket数组的指针，数组的大小为2^B

  • oldbuckets：扩容阶段用于记录旧桶使用的溢出桶的地址，仅仅在扩容时非空

  • nevacuate：扩容阶段要迁移的下一个旧桶编号

  • extra：指向mapextar的指针，记录溢出桶相关信息

buckets是一个指向bmap的指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// A bucket for a Go map.
type bmap struct {
	tophash [abi.OldMapBucketCount]uint8
}
//上面bmap结构是静态结构，在编译过程中runtime.bmap会拓展成以下结构体：
type bmap struct{
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr        // 内存对齐使用，可能不需要
    overflow uintptr        // 当bucket 的8个key 存满了之后
    // overflow 指向下一个溢出桶 bmap，
    // overflow是uintptr而不是*bmap类型，保证bmap完全不含指针，是为了减少gc，溢出桶存储到extra字段中
}

在Go中，我们定义的Map数组底层是hmap。

hmap中的buckets指向bmap列表，每个bmap中保存了8个key=>value键值对和指向溢出桶的位置overflow。所以实际数据是存在一个个bucket中。

整体结构

map_struct.drawio.png

查询

  1. 当我们查询时，go会将key通过hash成64位[由于当前主流机都是64位操作系统，所以计算结果有64个比特位]。
  2. 通过低B位确定在哪一个桶中，这里的B就是hmap中的B字段。
  3. 然后遍历桶中的key，这里的key是tophash，是key经过hash之后的高8位。
  4. 如果遍历到tophash相同，则再对比key。
  5. 如果key相同则查询成功。
  6. 如果桶中没有查询到，则会去关联的溢出桶中重复查找。

bucket桶中的key存的是key经过hash后的高8位即tophash。tophash可以帮助快速定位key的位置。如果高8位都不同，则肯定不匹配了。

新增

  1. 当我们向Map中put一条数据时，go会将key通过hash成64位。
  2. 通过hashkey的后B位，确定应该存在哪一个bucket桶中。
  3. 如果bucket桶中key不满8个，则直接添加到第一个槽位。
  4. 如果bucket桶中key已经达到8个，则会存入溢出桶的第一个空的槽位中，如果没有溢出桶，则创建溢出桶，添加到溢出桶的第一个空的槽位。

删除

  1. 查询到对应的位置
  2. 将该槽位的tophash标记为已删除emptyOne/emptyRest
  3. 内存不会立刻释放。后续的插入可能会重新占用已删除的槽位。
  4. 在重排整理后会释放占用的槽位。

扩容/重排

map的扩容有两种，等量扩容、2倍扩容

等量扩容/重排整理（sameSizeGrow）

这种扩容，会将原本松散的key分布重新整理。将桶中的后置位提前。减少溢出桶数量，但不会减少桶的数量，即hmap中的B数。

  1. 重新分配所有的元素到桶结构中
  2. 合并桶下的溢出桶

触发条件

1
2
3
4
5
6
7
8
9
10
// runtime/map.go
func hashGrow(t *maptype, h *hmap) {
    // 判断是否需要整理而非扩容
    if !overLoadFactor(h.count+1, h.B) && 
       (h.noverflow > uint16(1)<<(h.B&15)) { // 溢出桶过多
        // 触发 sameSizeGrow（不改变桶数量）
        h.flags |= sameSizeGrow
    }
    // 创建新桶并迁移数据
}
  • 元素数量 超过负载因子阈值(6.5*2^B)，但溢出桶数量过多(超过 2^(B&15))。
  • 删除导致大量空槽位，且 溢出桶 的利用率低。

2倍扩容

原本的桶数量不够使用，会创建一个新的大的桶数组，oldbuckets指向旧桶，每次操作时迁移最多2个旧桶，直到所有的桶里数据都迁移完。期间会将数据重排。

  1. 初始化新桶，数量翻倍，更新B数。buckets指向新桶，oldbuckets指向旧桶。
  2. 每次插入/删除/修改操作最多迁移两个旧桶。
  3. 在扩容没有完成之前，get操作在旧桶未迁移的情况下会在旧桶和新桶查询两次。
  4. 旧桶迁移完成后，删除oldbucket引用，等待GC回收。

触发条件

1
2
3
4
// runtime/map.go
func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt*(1<<B) && (1<<B) >= bucketCnt
}
  • 元素数量 超过负载因子：count > 6.5 * 2^B，负载因子=6.5。
  • 溢出桶 过多：溢出桶数量超过2^(B&15)

线程不安全

在同一时刻多个goroutine对map进行读写是不安全的。写入可能会触发扩容，改变到B值。影响到元素分布的桶位置。

一般通过Mutex锁来处理控制并发读写。

不可对Map数据进行取址操作，因为扩容会导致之前的地址无效。

更新于：2025年3月14日

技术

Go

基础

评论